"""
Problem 36: https://projecteuler.net/problem=36

The number 3797 has an interesting property. Being prime itself, it is possible
to continuously remove digits from left to right, and remain prime at each stage:
3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right
and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/12
'''

'''
main operator of this question is primality testing. 
there are two kinds of thinking:
    1. get primes table in advance
    2. temporary testing, and save the result

the truncatable primes just have limited digitis, beacause any number(> 10) 
meeting the following any condition is not truncatable prime
    1. started with 1 or 9 
    2. ended with 1 or 9
    3. contained 0,4,6 or 8
    4. contained 2 or 5 besides the top digit

so, there are many numbers don't needing primality testing.
e.g, the number (d6,d5,d4,d3,d2,d1) consisting of 6 digits,
    d6 = 2,3,5,7,           4 kinds
    d1 = 3,7,               2 kinds
    d5,d4,d3,d2 = 1,3,7,9,  4 kinds
    we can just need jugding 4*2*(4*4*4*4) = 2048 numbers, 
    in other words, excluding 900000-2024=897952 numbers(6-digit) simply.

    more generally, for d-digits numbers, 
                        it is 4*2*(4^(d-2)) = 0.5*4^d
                    for numbers less than 10^d, 
                        it is 0.5*(4^2 + 4^3 +...+ 4^d) = (4^(d+1)-8)/6  
                    camparing with 10^d, 
                            (4^(d+1)-8)/6  /
                                          /                     ~=  0.667*(0.4)^d
                                         /  10^d                    (e.g. d=24, 1.9E-10)
                    further camparing with the numbers of primes less than n:
                            pi(n) ~= n/(ln n) = 10^d / (ln 10^d)
                            (4^(d+1)-8)/6  /
                                          /                     ~=  1.535*d*(0.4)^d
                                         / 10^d/(ln 10^d)           (e.g. d=29, 1.3E-10)

obviously, the second thinking is more effective than
           generating prime table in the first thinking.
           by saving the temporary testing result, it will has better acceleration.


'''
import p035  # p035.isPrime
PrimesDict = {0: 0, 1: 0, 2: 1, 3: 1, 4: 0,
              5: 1, 6: 0, 7: 1, 8: 0, 9: 0, 10: 0}


def isPrimeD(n: int) -> bool:
    global PrimesDict
    if n in PrimesDict:
        return PrimesDict[n]
    else:
        b = p035.isPrime(n)
        PrimesDict[n] = b
        return b


'''
N = 7
maxNum = 10**N
maxNum_sqrt = int(maxNum**0.5)
PrimesDict = [True]*(maxNum+1)
PrimesDict[0] = False
PrimesDict[1] = False
PrimesDict[2] = True

i = 2
while i < maxNum_sqrt+1:
    if PrimesDict[i]:
        for j in range(i, maxNum//i+1):  # for i-1, have handled by i-1,j
            PrimesDict[i*j] = False
    i += 1


def isPrimeD(n: int) -> bool:
    global PrimesDict
    return PrimesDict[n]
'''


def isTruncatablePrime(n: int) -> bool:
    '''
    primes that are both truncatable from left to right and right to left

    >>> assert isTruncatablePrime(3797)
    '''
    global PrimesDict

    if n <= 10:
        return False

    ns = str(n)

    if any([ns.startswith('1'), ns.startswith('9'),
            ns.endswith('1'), ns.endswith('9')]):
        return False

    if any(['0' in ns, '4' in ns, '6' in ns, '8' in ns,
            '2' in ns[1:], '5' in ns[1:]]):
        return False

    if not isPrimeD(n):
        return False

    nsl = ns[:-1]
    nsr = ns[1:]

    while nsl:
        if not isPrimeD(int(nsl)) or not isPrimeD(int(nsr)):
            return False

        nsl = nsl[:-1]
        nsr = nsr[1:]

    return True


def solution(total: int = 11) -> int:
    '''
    Find the sum of the only eleven primes 
    that are both truncatable from left to right and right to left.
    '''
    i = 11
    count = 0
    res = 0
    while count < total:
        i += 2
        if isTruncatablePrime(i):
            print('TruncatablePrime: ', i)
            count += 1
            res += i
    return res


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print('sum: ', solution())
    # 748317
    print('size of PrimesDict: ', len(PrimesDict))
    # 2785 numbers

    '''
    23
    37
    53
    73
    313
    317
    373
    797
    3137
    3797
    739397
    '''
